// Copyright 2003-2009 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ========================================================================
//
// Implemetation of CRCs (aka Rabin Fingerprints).
// Treats the input as a polynomial with coefficients in Z(2),
// and finds the remainder when divided by an irreducible polynomial
// of the appropriate length.
// It handles all CRC sizes from 8 to 128 bits.
// It's somewhat complicated by having separate implementations optimized for
// CRC's <=32 bits, <= 64 bits, and <= 128 bits.
// The input string is prefixed with a "1" bit, and has "degree" "0" bits
// appended to it before the remainder is found.   This ensures that
// short strings are scrambled somewhat and that strings consisting
// of all nulls have a non-zero CRC.

#include <stddef.h>
#include "omaha/base/crc.h"
#include "omaha/base/debug.h"
#include "omaha/base/commontypes.h"

namespace omaha {

static const int SMALL_BITS = 8;
                   // When extending an input with a string of zeroes,
                   // if the number of zeroes is less than 2**SMALL_BITS,
                   // a normal Extend is done, rather than a polynomial
                   // multiplication.
static const char zeroes[1 << SMALL_BITS] = { 0 };  // an array of zeroes

static const uint8 *zero_ptr = 0;   // The 0 pointer---used for alignment

// These are used to index a 2-entry array of words that together
// for a longer integer.  LO indexes the low-order half.
#define LO 0
#define HI (1-LO)

// Constructor and destructor for baseclase CRC.
CRC::~CRC() {}
CRC::CRC() {}

struct CRC_pair {             // Used to represent a 128-bit value
  uint64 lo;
  uint64 hi;
};

class CRCImpl : public CRC {    // Implemention of the abstract class CRC
 public:
  CRCImpl() {}
  virtual ~CRCImpl() {}

  // The internal version of CRC::New().
  static CRCImpl *NewInternal(uint64 lo, uint64 hi,
                              int degree, size_t roll_length);

  virtual void Empty(uint64 *lo, uint64 *hi) const;

  size_t roll_length_;    // length of window in rolling CRC
  int degree_;            // bits in the CRC
  uint64 poly_lo_;        // The CRC of the empty string, low part
  uint64 poly_hi_;        // The CRC of the empty string, high part

 private:
  DISALLOW_EVIL_CONSTRUCTORS(CRCImpl);
};

// This is the 32-bit implementation.  It handles all sizes from 8 to 32.
class CRC32 : public CRCImpl {
 public:
  CRC32() {}
  virtual ~CRC32() {}

  virtual void Extend(uint64 *lo, uint64 *hi,
                      const void *bytes, size_t length) const;
  virtual void ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const;
  virtual void Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const;

  uint32 table0_[256];  // table of byte extensions
  uint32 table1_[256];  // table of byte extensions, shifted by 1 byte
  uint32 table2_[256];  // table of byte extensions, shifted by 2 bytes
  uint32 table3_[256];  // table of byte extensions, shifted by 3 bytes
  uint32 roll_[256];    // table of byte roll values
  uint32 zeroes_[256];  // table of zero extensions

 private:
  DISALLOW_EVIL_CONSTRUCTORS(CRC32);
};

static const uint64 UINT64_ZERO = 0;    // a 64-bit zero
static const uint64 UINT64_ONE = 1;     // a 64-bit 1

// The B() macro sets the bit corresponding to X**(_x) in the polynomial
#define B(_x) (UINT64_ONE << ((_x) < 64?(63-(_x)):(127-(_x))))

// Used to initialize polynomials.
// The redundant tests on _len are to avoid warnings from the
// compiler about inappropriate shift lengths.   These shifts
// occur on not-taken branch of the ?: in some cases.
#define kDefPoly(_h,_l,_len) \
 { ((_len) <= 64  ? (_l) >> ((_len) <= 64? 64 - (_len): 0) : \
    (_len) == 128 ? (_h) : \
                     ((_h) >> ((_len) > 64? 128 - (_len): 0)) | \
                     ((_l) << ((_len) > 64 && (_len) < 128? (_len)-64: 0))), \
   ((_len) <= 64  ? 0 : \
    (_len) == 128 ? (_l) :  \
                    (_l) >> ((_len) > 64? 128 - (_len): 0)), \
   (_len) }

// A table of irreducible polynomials suitable for use with the implementation.
// Indexes 0...1 have degree 32 polynomials.
// Indexes 2...3 have degree 64 polynomials.
// Indexes 4...5 have degree 96 polynomials.
// Indexes 6...7 have degree 128 polynomials.
// Index i=8...128 has a degree i polynomial.
// All polynomials in the table are guaranteed distinct.
// lint -save -e572 -e648 -e778   Excessive shift value, expression evaluates to 0
static const struct CRC::Poly poly_list[] = {
 kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(23)+B(20)+B(17)+B(15)+B(14)+
          B(12)+B(6)+B(5)+B(2)+B(0), 32),
 kDefPoly(UINT64_ZERO, B(31)+B(28)+B(27)+B(26)+B(24)+B(22)+B(19)+B(18)+B(16)+
          B(13)+B(11)+B(10)+B(9)+B(4)+B(2)+B(0), 32),
 kDefPoly(UINT64_ZERO, B(60)+B(59)+B(58)+B(56)+B(55)+B(54)+B(51)+B(50)+B(49)+
          B(48)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+
          B(32)+B(31)+B(30)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+B(19)+
          B(17)+B(16)+B(15)+B(8)+B(7)+B(6)+B(5)+B(0), 64),
 kDefPoly(UINT64_ZERO, B(63)+B(62)+B(60)+B(58)+B(57)+B(56)+B(54)+B(52)+B(46)+
          B(45)+B(43)+B(40)+B(37)+B(36)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+
          B(28)+B(27)+B(26)+B(23)+B(19)+B(18)+B(15)+B(14)+B(13)+B(9)+B(8)+
          B(0), 64),
 kDefPoly(B(95)+B(94)+B(91)+B(90)+B(89)+B(88)+B(87)+B(86)+B(79)+B(78)+
          B(77)+B(76)+B(75)+B(74)+B(73)+B(69)+B(68)+B(66), B(63)+B(61)+
          B(59)+B(57)+B(53)+B(51)+B(50)+B(47)+B(40)+B(39)+B(38)+B(36)+
          B(35)+B(33)+B(29)+B(28)+B(27)+B(25)+B(24)+B(23)+B(21)+B(19)+
          B(18)+B(17)+B(16)+B(13)+B(12)+B(10)+B(9)+B(7)+B(4)+B(2)+B(1)+
          B(0), 96),
 kDefPoly(B(95)+B(92)+B(89)+B(88)+B(87)+B(85)+B(84)+B(82)+B(81)+B(80)+
          B(79)+B(78)+B(76)+B(75)+B(70)+B(69)+B(66)+B(65), B(60)+B(56)+
          B(55)+B(52)+B(51)+B(49)+B(48)+B(46)+B(44)+B(42)+B(41)+B(39)+
          B(38)+B(37)+B(35)+B(33)+B(32)+B(30)+B(28)+B(27)+B(25)+B(22)+
          B(19)+B(17)+B(14)+B(12)+B(10)+B(0), 96),
 kDefPoly(B(122)+B(121)+B(120)+B(119)+B(117)+B(116)+B(114)+B(113)+B(112)+
          B(111)+B(109)+B(107)+B(104)+B(102)+B(100)+B(98)+B(96)+B(94)+
          B(93)+B(92)+B(91)+B(90)+B(88)+B(87)+B(86)+B(84)+B(82)+B(80)+
          B(75)+B(74)+B(73)+B(69), B(62)+B(61)+B(58)+B(52)+B(48)+B(47)+
          B(46)+B(45)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(31)+
          B(30)+B(28)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+
          B(10)+B(9)+B(8)+B(7)+B(5)+B(2)+B(1)+B(0), 128),
 kDefPoly(B(127)+B(126)+B(124)+B(121)+B(117)+B(116)+B(115)+B(113)+B(112)+
          B(111)+B(108)+B(105)+B(104)+B(103)+B(100)+B(98)+B(96)+B(93)+
          B(92)+B(90)+B(89)+B(88)+B(86)+B(85)+B(80)+B(77)+B(76)+B(72)+
          B(70)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(56)+
          B(53)+B(52)+B(51)+B(50)+B(48)+B(46)+B(39)+B(35)+B(34)+B(33)+
          B(32)+B(30)+B(29)+B(28)+B(22)+B(21)+B(19)+B(18)+B(17)+B(14)+
          B(10)+B(9)+B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 128),
 kDefPoly(UINT64_ZERO, B(7)+B(6)+B(5)+B(4)+B(2)+B(0), 8),
 kDefPoly(UINT64_ZERO, B(8)+B(4)+B(3)+B(2)+B(1)+B(0), 9),
 kDefPoly(UINT64_ZERO, B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 10),
 kDefPoly(UINT64_ZERO, B(10)+B(9)+B(7)+B(5)+B(1)+B(0), 11),
 kDefPoly(UINT64_ZERO, B(11)+B(10)+B(5)+B(2)+B(1)+B(0), 12),
 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(10)+B(8)+B(5)+B(3)+B(2)+B(0), 13),
 kDefPoly(UINT64_ZERO, B(11)+B(10)+B(9)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+
          B(0), 14),
 kDefPoly(UINT64_ZERO, B(14)+B(12)+B(11)+B(10)+B(9)+B(5)+B(3)+B(2)+B(1)+
          B(0), 15),
 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 16),
 kDefPoly(UINT64_ZERO, B(16)+B(14)+B(11)+B(10)+B(8)+B(3)+B(1)+B(0), 17),
 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(9)+B(8)+B(7)+B(4)+B(3)+B(0), 18),
 kDefPoly(UINT64_ZERO, B(12)+B(11)+B(8)+B(7)+B(6)+B(5)+B(2)+B(0), 19),
 kDefPoly(UINT64_ZERO, B(18)+B(15)+B(14)+B(12)+B(9)+B(6)+B(3)+B(0), 20),
 kDefPoly(UINT64_ZERO, B(20)+B(19)+B(14)+B(13)+B(12)+B(11)+B(8)+B(7)+B(6)+
          B(5)+B(2)+B(0), 21),
 kDefPoly(UINT64_ZERO, B(21)+B(20)+B(18)+B(16)+B(15)+B(14)+B(12)+B(9)+B(7)+
          B(2)+B(1)+B(0), 22),
 kDefPoly(UINT64_ZERO, B(22)+B(21)+B(17)+B(16)+B(15)+B(14)+B(12)+B(10)+B(7)+
          B(4)+B(1)+B(0), 23),
 kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(14)+B(12)+B(4)+
          B(0), 24),
 kDefPoly(UINT64_ZERO, B(24)+B(23)+B(22)+B(20)+B(18)+B(17)+B(14)+B(13)+B(9)+
          B(0), 25),
 kDefPoly(UINT64_ZERO, B(25)+B(22)+B(21)+B(19)+B(17)+B(15)+B(14)+B(12)+B(11)+
          B(10)+B(6)+B(4)+B(3)+B(0), 26),
 kDefPoly(UINT64_ZERO, B(26)+B(25)+B(19)+B(17)+B(16)+B(13)+B(5)+B(4)+B(1)+
          B(0), 27),
 kDefPoly(UINT64_ZERO, B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(13)+B(12)+B(10)+
          B(9)+B(8)+B(6)+B(5)+B(3)+B(1)+B(0), 28),
 kDefPoly(UINT64_ZERO, B(27)+B(26)+B(25)+B(23)+B(22)+B(20)+B(19)+B(15)+B(14)+
          B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(0), 29),
 kDefPoly(UINT64_ZERO, B(29)+B(27)+B(25)+B(23)+B(20)+B(19)+B(18)+B(17)+B(16)+
          B(14)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+B(4)+B(0), 30),
 kDefPoly(UINT64_ZERO, B(30)+B(29)+B(28)+B(27)+B(25)+B(23)+B(22)+B(21)+B(20)+
          B(19)+B(18)+B(16)+B(15)+B(10)+B(9)+B(8)+B(4)+B(3)+B(1)+B(0), 31),
 kDefPoly(UINT64_ZERO, B(31)+B(29)+B(28)+B(27)+B(21)+B(20)+B(15)+B(13)+B(10)+
          B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(0), 32),
 kDefPoly(UINT64_ZERO, B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(22)+B(21)+
          B(19)+B(15)+B(10)+B(4)+B(3)+B(2)+B(0), 33),
 kDefPoly(UINT64_ZERO, B(30)+B(27)+B(26)+B(25)+B(24)+B(20)+B(19)+B(18)+B(16)+
          B(15)+B(14)+B(12)+B(9)+B(8)+B(7)+B(5)+B(1)+B(0), 34),
 kDefPoly(UINT64_ZERO, B(34)+B(32)+B(28)+B(27)+B(26)+B(22)+B(21)+B(20)+B(19)+
          B(14)+B(13)+B(12)+B(10)+B(6)+B(5)+B(4)+B(3)+B(0), 35),
 kDefPoly(UINT64_ZERO, B(35)+B(34)+B(33)+B(32)+B(31)+B(28)+B(26)+B(24)+B(22)+
          B(21)+B(20)+B(19)+B(18)+B(14)+B(13)+B(12)+B(10)+B(9)+B(8)+B(6)+B(5)+
          B(4)+B(3)+B(0), 36),
 kDefPoly(UINT64_ZERO, B(36)+B(35)+B(31)+B(30)+B(28)+B(26)+B(25)+B(23)+B(22)+
          B(20)+B(19)+B(18)+B(16)+B(13)+B(12)+B(7)+B(6)+B(4)+B(3)+B(0), 37),
 kDefPoly(UINT64_ZERO, B(37)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(28)+B(27)+
          B(26)+B(25)+B(23)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(9)+
          B(8)+B(7)+B(6)+B(2)+B(1)+B(0), 38),
 kDefPoly(UINT64_ZERO, B(38)+B(37)+B(33)+B(32)+B(31)+B(27)+B(25)+B(24)+B(21)+
          B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(8)+B(7)+B(6)+B(3)+B(2)+B(1)+
          B(0), 39),
 kDefPoly(UINT64_ZERO, B(38)+B(37)+B(35)+B(34)+B(32)+B(31)+B(30)+B(27)+B(24)+
          B(21)+B(20)+B(14)+B(13)+B(11)+B(8)+B(4)+B(2)+B(0), 40),
 kDefPoly(UINT64_ZERO, B(38)+B(36)+B(35)+B(34)+B(33)+B(31)+B(30)+B(29)+B(28)+
          B(27)+B(23)+B(22)+B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(11)+B(5)+
          B(4)+B(0), 41),
 kDefPoly(UINT64_ZERO, B(41)+B(37)+B(36)+B(35)+B(32)+B(31)+B(30)+B(29)+B(28)+
          B(25)+B(19)+B(18)+B(14)+B(13)+B(12)+B(7)+B(6)+B(4)+B(2)+B(0), 42),
 kDefPoly(UINT64_ZERO, B(42)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+B(33)+B(31)+
          B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(20)+B(19)+B(15)+B(11)+B(10)+
          B(9)+B(8)+B(6)+B(5)+B(3)+B(0), 43),
 kDefPoly(UINT64_ZERO, B(43)+B(42)+B(40)+B(39)+B(37)+B(35)+B(32)+B(30)+B(26)+
          B(25)+B(24)+B(20)+B(16)+B(13)+B(12)+B(11)+B(8)+B(6)+B(5)+B(4)+B(1)+
          B(0), 44),
 kDefPoly(UINT64_ZERO, B(43)+B(42)+B(41)+B(40)+B(39)+B(38)+B(33)+B(32)+B(27)+
          B(26)+B(25)+B(23)+B(20)+B(18)+B(17)+B(16)+B(14)+B(11)+B(10)+B(9)+
          B(6)+B(5)+B(1)+B(0), 45),
 kDefPoly(UINT64_ZERO, B(45)+B(43)+B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+
          B(29)+B(27)+B(25)+B(23)+B(18)+B(17)+B(16)+B(10)+B(9)+B(7)+B(6)+B(4)+
          B(3)+B(2)+B(0), 46),
 kDefPoly(UINT64_ZERO, B(45)+B(44)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+B(32)+
          B(30)+B(23)+B(21)+B(20)+B(17)+B(15)+B(13)+B(11)+B(10)+B(7)+B(5)+
          B(3)+B(0), 47),
 kDefPoly(UINT64_ZERO, B(46)+B(42)+B(41)+B(39)+B(37)+B(36)+B(35)+B(29)+B(28)+
          B(25)+B(24)+B(21)+B(20)+B(18)+B(17)+B(13)+B(12)+B(11)+B(10)+B(9)+
          B(8)+B(5)+B(1)+B(0), 48),
 kDefPoly(UINT64_ZERO, B(48)+B(44)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(35)+
          B(34)+B(30)+B(28)+B(27)+B(24)+B(21)+B(18)+B(17)+B(8)+B(3)+B(0), 49),
 kDefPoly(UINT64_ZERO, B(48)+B(47)+B(46)+B(45)+B(44)+B(43)+B(42)+B(35)+B(33)+
          B(29)+B(26)+B(24)+B(23)+B(21)+B(18)+B(16)+B(14)+B(13)+B(12)+B(9)+
          B(7)+B(6)+B(5)+B(4)+B(3)+B(0), 50),
 kDefPoly(UINT64_ZERO, B(47)+B(46)+B(45)+B(44)+B(43)+B(40)+B(39)+B(38)+B(36)+
          B(35)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+
          B(18)+B(17)+B(15)+B(11)+B(7)+B(4)+B(3)+B(0), 51),
 kDefPoly(UINT64_ZERO, B(51)+B(46)+B(43)+B(38)+B(37)+B(36)+B(34)+B(31)+B(27)+
          B(26)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(9)+B(7)+B(5)+B(1)+
          B(0), 52),
 kDefPoly(UINT64_ZERO, B(50)+B(49)+B(47)+B(46)+B(44)+B(42)+B(41)+B(37)+B(36)+
          B(35)+B(33)+B(29)+B(28)+B(26)+B(24)+B(23)+B(21)+B(20)+B(14)+B(13)+
          B(12)+B(11)+B(10)+B(9)+B(8)+B(6)+B(3)+B(2)+B(1)+B(0), 53),
 kDefPoly(UINT64_ZERO, B(52)+B(47)+B(46)+B(44)+B(43)+B(42)+B(40)+B(36)+B(32)+
          B(31)+B(30)+B(29)+B(28)+B(26)+B(25)+B(24)+B(23)+B(22)+B(20)+B(19)+
          B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(2)+
          B(0), 54),
 kDefPoly(UINT64_ZERO, B(53)+B(50)+B(48)+B(47)+B(37)+B(35)+B(31)+B(30)+B(25)+
          B(22)+B(21)+B(20)+B(19)+B(18)+B(15)+B(10)+B(8)+B(6)+B(3)+B(2)+B(1)+
          B(0), 55),
 kDefPoly(UINT64_ZERO, B(54)+B(52)+B(51)+B(49)+B(48)+B(42)+B(38)+B(37)+B(31)+
          B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(19)+B(16)+B(12)+B(11)+B(8)+
          B(6)+B(4)+B(3)+B(0), 56),
 kDefPoly(UINT64_ZERO, B(55)+B(54)+B(51)+B(49)+B(48)+B(47)+B(46)+B(44)+B(43)+
          B(42)+B(41)+B(40)+B(39)+B(38)+B(32)+B(29)+B(27)+B(26)+B(23)+B(21)+
          B(20)+B(15)+B(12)+B(7)+B(6)+B(5)+B(3)+B(0), 57),
 kDefPoly(UINT64_ZERO, B(57)+B(54)+B(52)+B(47)+B(45)+B(42)+B(41)+B(40)+B(39)+
          B(36)+B(34)+B(33)+B(31)+B(28)+B(26)+B(21)+B(20)+B(18)+B(17)+B(16)+
          B(13)+B(11)+B(8)+B(7)+B(4)+B(2)+B(1)+B(0), 58),
 kDefPoly(UINT64_ZERO, B(58)+B(56)+B(54)+B(49)+B(47)+B(46)+B(43)+B(40)+B(38)+
          B(36)+B(35)+B(33)+B(32)+B(31)+B(30)+B(27)+B(24)+B(22)+B(21)+B(19)+
          B(17)+B(16)+B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(3)+B(2)+B(1)+B(0),
          59),
 kDefPoly(UINT64_ZERO, B(56)+B(54)+B(51)+B(46)+B(43)+B(42)+B(40)+B(39)+B(37)+
          B(35)+B(34)+B(33)+B(32)+B(31)+B(30)+B(29)+B(27)+B(25)+B(22)+B(21)+
          B(20)+B(19)+B(17)+B(16)+B(15)+B(14)+B(13)+B(12)+B(9)+B(7)+B(4)+
          B(3)+B(1)+B(0), 60),
 kDefPoly(UINT64_ZERO, B(59)+B(58)+B(57)+B(56)+B(54)+B(53)+B(50)+B(49)+B(47)+
          B(44)+B(42)+B(41)+B(40)+B(37)+B(35)+B(34)+B(32)+B(30)+B(29)+B(27)+
          B(26)+B(22)+B(21)+B(20)+B(17)+B(14)+B(13)+B(12)+B(8)+B(5)+B(4)+
          B(0), 61),
 kDefPoly(UINT64_ZERO, B(61)+B(59)+B(57)+B(55)+B(54)+B(53)+B(52)+B(51)+B(50)+
          B(49)+B(48)+B(45)+B(44)+B(40)+B(37)+B(35)+B(32)+B(31)+B(29)+B(25)+
          B(24)+B(23)+B(20)+B(17)+B(16)+B(15)+B(13)+B(12)+B(11)+B(10)+B(6)+
          B(5)+B(2)+B(0), 62),
 kDefPoly(UINT64_ZERO, B(62)+B(57)+B(56)+B(53)+B(52)+B(51)+B(50)+B(46)+B(41)+
          B(38)+B(35)+B(34)+B(33)+B(31)+B(27)+B(25)+B(23)+B(21)+B(19)+B(18)+
          B(17)+B(16)+B(13)+B(11)+B(7)+B(5)+B(1)+B(0), 63),
 kDefPoly(UINT64_ZERO, B(62)+B(61)+B(60)+B(57)+B(55)+B(54)+B(53)+B(49)+B(48)+
          B(46)+B(44)+B(42)+B(40)+B(39)+B(37)+B(36)+B(28)+B(27)+B(25)+B(23)+
          B(22)+B(21)+B(17)+B(15)+B(13)+B(7)+B(6)+B(4)+B(2)+B(0), 64),
 kDefPoly(UINT64_ZERO, B(63)+B(62)+B(59)+B(57)+B(54)+B(53)+B(51)+B(48)+
          B(47)+B(46)+B(45)+B(44)+B(41)+B(40)+B(38)+B(36)+B(35)+B(28)+
          B(25)+B(24)+B(21)+B(20)+B(18)+B(16)+B(15)+B(13)+B(11)+B(8)+B(7)+
          B(3)+B(1)+B(0), 65),
 kDefPoly(UINT64_ZERO, B(63)+B(58)+B(57)+B(56)+B(52)+B(51)+B(50)+B(44)+
          B(41)+B(40)+B(36)+B(34)+B(32)+B(31)+B(27)+B(25)+B(23)+B(21)+
          B(20)+B(19)+B(18)+B(17)+B(15)+B(14)+B(12)+B(11)+B(10)+B(8)+B(5)+
          B(4)+B(3)+B(0), 66),
 kDefPoly(B(66), B(62)+B(60)+B(59)+B(58)+B(57)+B(56)+B(55)+B(54)+B(52)+
          B(50)+B(47)+B(46)+B(45)+B(43)+B(42)+B(41)+B(38)+B(37)+B(36)+
          B(33)+B(32)+B(31)+B(30)+B(28)+B(27)+B(26)+B(24)+B(21)+B(18)+
          B(17)+B(14)+B(13)+B(12)+B(11)+B(10)+B(7)+B(4)+B(3)+B(0), 67),
 kDefPoly(B(67)+B(66), B(63)+B(61)+B(57)+B(55)+B(51)+B(47)+B(45)+B(43)+
          B(42)+B(41)+B(40)+B(39)+B(32)+B(31)+B(30)+B(28)+B(27)+B(25)+
          B(19)+B(18)+B(17)+B(15)+B(11)+B(9)+B(8)+B(7)+B(6)+B(5)+B(4)+B(3)+
          B(1)+B(0), 68),
 kDefPoly(B(68), B(60)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+B(48)+B(44)+
          B(40)+B(38)+B(37)+B(33)+B(31)+B(28)+B(25)+B(22)+B(21)+B(20)+
          B(19)+B(18)+B(17)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+B(4)+B(1)+
          B(0), 69),
 kDefPoly(B(69)+B(68)+B(67)+B(66), B(63)+B(62)+B(61)+B(59)+B(51)+B(49)+
          B(48)+B(46)+B(45)+B(42)+B(40)+B(38)+B(36)+B(35)+B(33)+B(32)+
          B(30)+B(29)+B(27)+B(23)+B(22)+B(21)+B(16)+B(12)+B(5)+B(4)+B(1)+
          B(0), 70),
 kDefPoly(B(70)+B(69)+B(68)+B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+
          B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+B(47)+B(44)+B(43)+B(41)+
          B(39)+B(37)+B(36)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(21)+
          B(20)+B(19)+B(17)+B(12)+B(11)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+
          B(0), 71),
 kDefPoly(B(71)+B(69)+B(68)+B(65)+B(64), B(62)+B(61)+B(59)+B(58)+B(55)+
          B(53)+B(51)+B(49)+B(48)+B(47)+B(43)+B(40)+B(38)+B(37)+B(36)+
          B(35)+B(33)+B(32)+B(31)+B(30)+B(29)+B(26)+B(24)+B(19)+B(18)+
          B(15)+B(13)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 72),
 kDefPoly(B(71)+B(70)+B(69)+B(67)+B(65), B(63)+B(62)+B(61)+B(58)+B(57)+
          B(56)+B(55)+B(52)+B(51)+B(50)+B(49)+B(46)+B(45)+B(44)+B(43)+
          B(41)+B(37)+B(36)+B(34)+B(33)+B(27)+B(26)+B(25)+B(21)+B(19)+
          B(18)+B(16)+B(15)+B(14)+B(13)+B(9)+B(8)+B(6)+B(5)+B(2)+B(1)+
          B(0), 73),
 kDefPoly(B(73)+B(71)+B(70)+B(65)+B(64), B(62)+B(60)+B(55)+B(54)+B(52)+
          B(50)+B(48)+B(47)+B(46)+B(44)+B(41)+B(40)+B(31)+B(29)+B(28)+
          B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(16)+B(12)+B(9)+B(6)+B(5)+
          B(4)+B(2)+B(0), 74),
 kDefPoly(B(74)+B(73)+B(72)+B(67)+B(64), B(63)+B(61)+B(60)+B(58)+B(57)+
          B(56)+B(54)+B(52)+B(51)+B(50)+B(44)+B(43)+B(42)+B(41)+B(40)+
          B(39)+B(38)+B(36)+B(35)+B(33)+B(32)+B(31)+B(29)+B(28)+B(26)+
          B(23)+B(21)+B(19)+B(18)+B(16)+B(15)+B(13)+B(12)+B(11)+B(7)+B(6)+
          B(5)+B(4)+B(3)+B(2)+B(0), 75),
 kDefPoly(B(75)+B(74)+B(71)+B(70)+B(66), B(63)+B(61)+B(59)+B(57)+B(53)+
          B(50)+B(49)+B(48)+B(44)+B(43)+B(42)+B(37)+B(33)+B(30)+B(27)+
          B(24)+B(23)+B(20)+B(18)+B(15)+B(12)+B(11)+B(9)+B(7)+B(6)+B(4)+
          B(3)+B(2)+B(0), 76),
 kDefPoly(B(73)+B(71)+B(70)+B(68)+B(67)+B(66)+B(65), B(63)+B(60)+B(59)+
          B(58)+B(57)+B(54)+B(49)+B(47)+B(46)+B(45)+B(43)+B(41)+B(38)+
          B(34)+B(33)+B(31)+B(30)+B(29)+B(27)+B(25)+B(24)+B(21)+B(20)+
          B(19)+B(16)+B(15)+B(14)+B(13)+B(10)+B(8)+B(6)+B(5)+B(4)+B(2)+
          B(0), 77),
 kDefPoly(B(77)+B(76)+B(75)+B(74)+B(70)+B(66)+B(65)+B(64), B(63)+B(62)+
          B(60)+B(58)+B(57)+B(55)+B(52)+B(51)+B(44)+B(41)+B(39)+B(38)+
          B(35)+B(31)+B(30)+B(29)+B(26)+B(22)+B(21)+B(20)+B(19)+B(15)+
          B(13)+B(11)+B(6)+B(4)+B(1)+B(0), 78),
 kDefPoly(B(78)+B(76)+B(75)+B(71)+B(68)+B(67)+B(65), B(63)+B(61)+B(60)+
          B(55)+B(54)+B(51)+B(50)+B(48)+B(44)+B(42)+B(41)+B(40)+B(38)+
          B(35)+B(34)+B(32)+B(28)+B(26)+B(23)+B(22)+B(19)+B(15)+B(13)+
          B(12)+B(8)+B(7)+B(5)+B(2)+B(0), 79),
 kDefPoly(B(77)+B(76)+B(75)+B(73)+B(70)+B(66), B(63)+B(61)+B(60)+B(59)+
          B(56)+B(54)+B(53)+B(52)+B(50)+B(44)+B(43)+B(40)+B(39)+B(38)+
          B(35)+B(34)+B(33)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+B(23)+
          B(22)+B(21)+B(20)+B(18)+B(16)+B(13)+B(12)+B(11)+B(10)+B(8)+B(7)+
          B(6)+B(3)+B(2)+B(1)+B(0), 80),
 kDefPoly(B(78)+B(77)+B(76)+B(75)+B(73)+B(71)+B(67)+B(66)+B(65)+
          B(64), B(61)+B(54)+B(53)+B(52)+B(49)+B(47)+B(44)+B(41)+B(40)+
          B(35)+B(33)+B(31)+B(30)+B(28)+B(27)+B(26)+B(25)+B(22)+B(21)+
          B(20)+B(16)+B(15)+B(13)+B(12)+B(11)+B(0), 81),
 kDefPoly(B(81)+B(80)+B(79)+B(77)+B(76)+B(74)+B(73)+B(72)+B(68)+B(67)+
          B(66)+B(64), B(62)+B(51)+B(50)+B(49)+B(47)+B(46)+B(45)+B(43)+
          B(41)+B(38)+B(37)+B(34)+B(32)+B(30)+B(27)+B(26)+B(25)+B(24)+
          B(23)+B(22)+B(20)+B(19)+B(16)+B(15)+B(13)+B(12)+B(9)+B(7)+B(5)+
          B(4)+B(1)+B(0), 82),
 kDefPoly(B(82)+B(81)+B(79)+B(78)+B(77)+B(75)+B(72)+B(71)+B(69)+B(68)+
          B(67)+B(66)+B(65)+B(64), B(60)+B(58)+B(57)+B(56)+B(53)+B(52)+
          B(51)+B(49)+B(48)+B(45)+B(43)+B(41)+B(40)+B(39)+B(38)+B(37)+
          B(36)+B(35)+B(33)+B(26)+B(24)+B(21)+B(19)+B(16)+B(13)+B(12)+
          B(11)+B(9)+B(7)+B(5)+B(4)+B(3)+B(1)+B(0), 83),
 kDefPoly(B(79)+B(77)+B(73)+B(72)+B(71)+B(66)+B(64), B(62)+B(61)+B(59)+
          B(58)+B(57)+B(56)+B(53)+B(52)+B(51)+B(48)+B(47)+B(46)+B(45)+
          B(43)+B(42)+B(41)+B(38)+B(37)+B(35)+B(33)+B(32)+B(29)+B(24)+
          B(22)+B(17)+B(16)+B(15)+B(13)+B(11)+B(10)+B(9)+B(7)+B(6)+B(5)+
          B(0), 84),
 kDefPoly(B(83)+B(78)+B(76)+B(73)+B(70)+B(69)+B(68)+B(67)+B(66)+
          B(64), B(62)+B(61)+B(60)+B(59)+B(54)+B(51)+B(50)+B(48)+B(47)+
          B(42)+B(41)+B(40)+B(38)+B(37)+B(36)+B(34)+B(31)+B(30)+B(28)+
          B(27)+B(26)+B(24)+B(22)+B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+
          B(14)+B(13)+B(12)+B(10)+B(6)+B(4)+B(0), 85),
 kDefPoly(B(84)+B(77)+B(76)+B(75)+B(71)+B(70)+B(69)+B(67)+B(65), B(63)+
          B(62)+B(59)+B(58)+B(57)+B(55)+B(53)+B(52)+B(51)+B(48)+B(47)+
          B(45)+B(43)+B(40)+B(38)+B(36)+B(34)+B(33)+B(31)+B(27)+B(25)+
          B(24)+B(23)+B(22)+B(19)+B(15)+B(13)+B(12)+B(11)+B(8)+B(6)+B(4)+
          B(0), 86),
 kDefPoly(B(85)+B(84)+B(83)+B(81)+B(80)+B(78)+B(73)+B(72)+B(70)+B(68)+
          B(67)+B(64), B(61)+B(60)+B(58)+B(57)+B(55)+B(52)+B(50)+B(49)+
          B(47)+B(44)+B(37)+B(36)+B(35)+B(34)+B(32)+B(31)+B(30)+B(25)+
          B(24)+B(23)+B(20)+B(13)+B(12)+B(11)+B(10)+B(9)+B(7)+B(6)+B(4)+
          B(3)+B(2)+B(0), 87),
 kDefPoly(B(86)+B(85)+B(84)+B(83)+B(82)+B(80)+B(77)+B(74)+B(70)+B(69)+
          B(65), B(63)+B(60)+B(59)+B(57)+B(56)+B(55)+B(53)+B(50)+B(49)+
          B(48)+B(45)+B(42)+B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(25)+
          B(21)+B(19)+B(13)+B(11)+B(8)+B(5)+B(4)+B(2)+B(1)+B(0), 88),
 kDefPoly(B(86)+B(85)+B(83)+B(82)+B(81)+B(78)+B(77)+B(74)+B(73)+B(72)+
          B(70)+B(69)+B(68)+B(65)+B(64), B(59)+B(57)+B(55)+B(54)+B(51)+
          B(50)+B(46)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(37)+B(33)+
          B(31)+B(30)+B(29)+B(28)+B(27)+B(23)+B(22)+B(21)+B(20)+B(18)+
          B(17)+B(16)+B(15)+B(10)+B(9)+B(3)+B(1)+B(0), 89),
 kDefPoly(B(86)+B(83)+B(82)+B(80)+B(79)+B(73)+B(70)+B(69)+B(67)+
          B(64), B(63)+B(62)+B(61)+B(57)+B(56)+B(54)+B(51)+B(49)+B(47)+
          B(46)+B(45)+B(40)+B(39)+B(37)+B(35)+B(33)+B(32)+B(29)+B(28)+
          B(27)+B(25)+B(24)+B(23)+B(22)+B(21)+B(20)+B(19)+B(18)+B(17)+
          B(15)+B(9)+B(8)+B(7)+B(3)+B(2)+B(0), 90),
 kDefPoly(B(90)+B(89)+B(84)+B(81)+B(80)+B(78)+B(74)+B(73)+B(71)+B(68)+
          B(64), B(60)+B(59)+B(58)+B(57)+B(55)+B(54)+B(52)+B(50)+B(49)+
          B(47)+B(45)+B(42)+B(41)+B(39)+B(38)+B(36)+B(32)+B(28)+B(25)+
          B(21)+B(20)+B(19)+B(15)+B(12)+B(11)+B(9)+B(8)+B(3)+
          B(0), 91),
 kDefPoly(B(91)+B(89)+B(88)+B(87)+B(86)+B(85)+B(84)+B(83)+B(80)+B(78)+
          B(76)+B(72)+B(70)+B(68), B(63)+B(62)+B(61)+B(59)+B(57)+B(56)+
          B(52)+B(51)+B(50)+B(49)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+
          B(34)+B(33)+B(32)+B(26)+B(25)+B(24)+B(23)+B(22)+B(18)+B(15)+
          B(12)+B(11)+B(9)+B(7)+B(6)+B(3)+B(1)+B(0), 92),
 kDefPoly(B(86)+B(85)+B(83)+B(82)+B(79)+B(78)+B(77)+B(75)+B(74)+B(73)+
          B(66)+B(64), B(59)+B(57)+B(56)+B(55)+B(54)+B(52)+B(51)+B(40)+
          B(38)+B(36)+B(34)+B(33)+B(28)+B(27)+B(26)+B(25)+B(23)+B(22)+
          B(21)+B(20)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+B(11)+B(8)+
          B(7)+B(6)+B(5)+B(4)+B(0), 93),
 kDefPoly(B(93)+B(92)+B(91)+B(89)+B(88)+B(87)+B(86)+B(81)+B(80)+B(75)+
          B(66)+B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(56)+B(54)+
          B(48)+B(47)+B(46)+B(45)+B(44)+B(42)+B(41)+B(38)+B(37)+B(36)+
          B(34)+B(33)+B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(13)+B(12)+
          B(11)+B(10)+B(8)+B(7)+B(4)+B(0), 94),
 kDefPoly(B(94)+B(88)+B(87)+B(82)+B(79)+B(78)+B(76)+B(73)+B(65)+
          B(64), B(62)+B(61)+B(60)+B(59)+B(58)+B(57)+B(53)+B(51)+B(50)+
          B(49)+B(48)+B(47)+B(46)+B(44)+B(40)+B(36)+B(34)+B(33)+B(30)+
          B(28)+B(27)+B(25)+B(22)+B(19)+B(18)+B(17)+B(16)+B(14)+B(7)+B(5)+
          B(3)+B(2)+B(1)+B(0), 95),
 kDefPoly(B(92)+B(89)+B(88)+B(86)+B(83)+B(79)+B(78)+B(76)+B(75)+B(74)+
          B(72)+B(70)+B(67)+B(66), B(63)+B(60)+B(57)+B(55)+B(53)+B(51)+
          B(47)+B(46)+B(44)+B(43)+B(42)+B(39)+B(38)+B(36)+B(34)+B(32)+
          B(31)+B(30)+B(27)+B(26)+B(25)+B(22)+B(21)+B(19)+B(17)+B(13)+
          B(11)+B(10)+B(9)+B(8)+B(7)+B(4)+B(1)+B(0), 96),
 kDefPoly(B(96)+B(94)+B(93)+B(91)+B(89)+B(87)+B(85)+B(83)+B(81)+B(78)+
          B(76)+B(74)+B(73)+B(68)+B(67)+B(64), B(62)+B(61)+B(57)+B(55)+
          B(54)+B(53)+B(49)+B(47)+B(41)+B(38)+B(35)+B(33)+B(28)+B(27)+
          B(24)+B(23)+B(21)+B(19)+B(18)+B(17)+B(15)+B(13)+B(12)+B(11)+B(8)+
          B(6)+B(4)+B(3)+B(1)+B(0), 97),
 kDefPoly(B(97)+B(93)+B(92)+B(91)+B(90)+B(87)+B(83)+B(82)+B(80)+B(77)+
          B(76)+B(75)+B(74)+B(73)+B(72)+B(70)+B(69)+B(68)+B(66)+B(65)+
          B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(57)+B(55)+B(53)+B(50)+
          B(49)+B(48)+B(45)+B(44)+B(43)+B(42)+B(40)+B(38)+B(36)+B(35)+
          B(34)+B(28)+B(27)+B(24)+B(22)+B(21)+B(18)+B(17)+B(16)+B(15)+
          B(14)+B(12)+B(11)+B(9)+B(8)+B(2)+B(1)+B(0), 98),
 kDefPoly(B(96)+B(94)+B(92)+B(86)+B(85)+B(84)+B(78)+B(77)+B(76)+B(75)+
          B(73)+B(71)+B(69)+B(68)+B(65), B(61)+B(59)+B(57)+B(56)+B(54)+
          B(50)+B(47)+B(46)+B(44)+B(41)+B(38)+B(36)+B(35)+B(34)+B(33)+
          B(32)+B(29)+B(27)+B(26)+B(25)+B(23)+B(22)+B(21)+B(19)+B(17)+
          B(16)+B(11)+B(9)+B(7)+B(6)+B(3)+B(2)+B(0), 99),
 kDefPoly(B(99)+B(96)+B(95)+B(93)+B(92)+B(88)+B(87)+B(83)+B(78)+B(77)+
          B(76)+B(75)+B(74)+B(73)+B(70)+B(66)+B(64), B(63)+B(62)+B(60)+
          B(59)+B(57)+B(56)+B(53)+B(50)+B(47)+B(41)+B(39)+B(38)+B(37)+
          B(34)+B(25)+B(23)+B(21)+B(20)+B(19)+B(18)+B(17)+B(16)+B(13)+B(9)+
          B(8)+B(6)+B(5)+B(1)+B(0), 100),
 kDefPoly(B(100)+B(98)+B(97)+B(95)+B(93)+B(92)+B(91)+B(89)+B(87)+B(85)+
          B(84)+B(82)+B(81)+B(80)+B(79)+B(76)+B(68)+B(66)+B(65), B(63)+
          B(62)+B(59)+B(57)+B(52)+B(51)+B(50)+B(47)+B(46)+B(45)+B(42)+
          B(41)+B(40)+B(39)+B(38)+B(37)+B(36)+B(34)+B(32)+B(31)+B(30)+
          B(24)+B(22)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+B(12)+B(11)+
          B(10)+B(8)+B(7)+B(5)+B(4)+B(2)+B(1)+B(0), 101),
 kDefPoly(B(101)+B(99)+B(97)+B(96)+B(92)+B(89)+B(88)+B(87)+B(86)+B(84)+
          B(82)+B(81)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+
          B(69), B(60)+B(59)+B(57)+B(56)+B(55)+B(54)+B(53)+B(51)+B(50)+
          B(49)+B(47)+B(45)+B(43)+B(41)+B(35)+B(34)+B(32)+B(31)+B(29)+
          B(27)+B(26)+B(25)+B(24)+B(21)+B(13)+B(12)+B(9)+B(8)+B(6)+B(5)+
          B(3)+B(0), 102),
 kDefPoly(B(101)+B(98)+B(97)+B(96)+B(94)+B(93)+B(92)+B(90)+B(89)+B(88)+
          B(87)+B(85)+B(83)+B(81)+B(80)+B(79)+B(76)+B(75)+B(71)+B(70)+
          B(69)+B(66), B(63)+B(62)+B(60)+B(59)+B(58)+B(56)+B(54)+B(53)+
          B(48)+B(45)+B(43)+B(42)+B(41)+B(37)+B(36)+B(32)+B(31)+B(30)+
          B(27)+B(25)+B(23)+B(22)+B(19)+B(16)+B(15)+B(11)+B(9)+B(5)+B(3)+
          B(0), 103),
 kDefPoly(B(98)+B(97)+B(95)+B(94)+B(91)+B(89)+B(88)+B(86)+B(85)+B(84)+
          B(81)+B(79)+B(78)+B(76)+B(74)+B(73)+B(70)+B(69)+B(68)+B(67)+
          B(66)+B(64), B(59)+B(53)+B(52)+B(51)+B(48)+B(46)+B(45)+B(43)+
          B(37)+B(34)+B(33)+B(31)+B(30)+B(28)+B(25)+B(22)+B(21)+B(20)+
          B(19)+B(14)+B(10)+B(8)+B(4)+B(2)+B(1)+B(0), 104),
 kDefPoly(B(103)+B(100)+B(99)+B(98)+B(94)+B(90)+B(89)+B(86)+B(84)+B(82)+
          B(79)+B(76)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(67)+
          B(66), B(63)+B(62)+B(59)+B(58)+B(57)+B(55)+B(51)+B(49)+B(48)+
          B(47)+B(46)+B(43)+B(42)+B(38)+B(36)+B(34)+B(33)+B(31)+B(30)+
          B(29)+B(28)+B(27)+B(24)+B(21)+B(20)+B(18)+B(17)+B(16)+B(14)+
          B(13)+B(11)+B(9)+B(7)+B(6)+B(5)+B(0), 105),
 kDefPoly(B(105)+B(104)+B(103)+B(102)+B(100)+B(98)+B(94)+B(93)+B(92)+B(91)+
          B(90)+B(89)+B(87)+B(86)+B(85)+B(83)+B(82)+B(81)+B(79)+B(77)+
          B(69)+B(68)+B(67)+B(64), B(61)+B(60)+B(59)+B(58)+B(56)+B(55)+
          B(53)+B(50)+B(48)+B(44)+B(40)+B(38)+B(37)+B(36)+B(35)+B(34)+
          B(33)+B(30)+B(29)+B(26)+B(22)+B(20)+B(13)+B(10)+B(8)+B(7)+B(5)+
          B(0), 106),
 kDefPoly(B(105)+B(101)+B(100)+B(98)+B(97)+B(96)+B(93)+B(92)+B(91)+B(90)+
          B(87)+B(86)+B(81)+B(79)+B(77)+B(75)+B(74)+B(72)+B(68)+B(67)+
          B(64), B(63)+B(62)+B(61)+B(60)+B(59)+B(58)+B(54)+B(53)+B(52)+
          B(50)+B(48)+B(47)+B(45)+B(42)+B(41)+B(38)+B(32)+B(29)+B(27)+
          B(26)+B(24)+B(21)+B(19)+B(18)+B(16)+B(15)+B(14)+B(13)+B(12)+
          B(10)+B(7)+B(6)+B(4)+B(1)+B(0), 107),
 kDefPoly(B(106)+B(105)+B(102)+B(100)+B(97)+B(95)+B(90)+B(89)+B(88)+B(86)+
          B(83)+B(82)+B(81)+B(79)+B(78)+B(75)+B(72)+B(66)+B(64), B(63)+
          B(62)+B(59)+B(58)+B(56)+B(54)+B(52)+B(51)+B(50)+B(48)+B(46)+
          B(45)+B(44)+B(42)+B(40)+B(37)+B(36)+B(35)+B(33)+B(29)+B(27)+
          B(22)+B(19)+B(17)+B(14)+B(12)+B(11)+B(10)+B(9)+B(8)+B(7)+B(6)+
          B(5)+B(3)+B(0), 108),
 kDefPoly(B(108)+B(102)+B(101)+B(100)+B(99)+B(98)+B(96)+B(95)+B(94)+B(90)+
          B(89)+B(88)+B(87)+B(84)+B(83)+B(81)+B(80)+B(77)+B(76)+B(75)+
          B(71)+B(67)+B(65), B(63)+B(61)+B(60)+B(54)+B(50)+B(49)+B(48)+
          B(43)+B(40)+B(39)+B(38)+B(36)+B(34)+B(29)+B(28)+B(27)+B(22)+
          B(21)+B(19)+B(16)+B(14)+B(13)+B(12)+B(10)+B(9)+B(7)+B(6)+B(5)+
          B(3)+B(2)+B(0), 109),
 kDefPoly(B(109)+B(108)+B(107)+B(102)+B(101)+B(98)+B(97)+B(96)+B(94)+B(92)+
          B(91)+B(90)+B(88)+B(87)+B(85)+B(84)+B(83)+B(82)+B(81)+B(80)+
          B(79)+B(78)+B(74)+B(73)+B(71)+B(70)+B(69)+B(66)+B(64), B(61)+
          B(58)+B(57)+B(56)+B(50)+B(49)+B(46)+B(44)+B(43)+B(41)+B(36)+
          B(35)+B(34)+B(30)+B(29)+B(26)+B(25)+B(24)+B(22)+B(21)+B(17)+
          B(13)+B(11)+B(9)+B(4)+B(1)+B(0), 110),
 kDefPoly(B(110)+B(109)+B(105)+B(98)+B(97)+B(95)+B(94)+B(93)+B(92)+B(90)+
          B(88)+B(84)+B(83)+B(82)+B(80)+B(77)+B(75)+B(72)+B(71)+B(70)+
          B(69)+B(66), B(63)+B(61)+B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+
          B(51)+B(50)+B(49)+B(47)+B(43)+B(40)+B(36)+B(35)+B(34)+B(33)+
          B(31)+B(27)+B(26)+B(21)+B(20)+B(19)+B(17)+B(16)+B(12)+B(8)+B(6)+
          B(4)+B(3)+B(2)+B(1)+B(0), 111),
 kDefPoly(B(109)+B(107)+B(106)+B(104)+B(100)+B(98)+B(96)+B(95)+B(94)+B(92)+
          B(91)+B(90)+B(89)+B(88)+B(86)+B(84)+B(81)+B(79)+B(78)+B(77)+
          B(75)+B(73)+B(71)+B(70)+B(69)+B(67)+B(64), B(63)+B(62)+B(61)+
          B(60)+B(58)+B(56)+B(54)+B(52)+B(51)+B(49)+B(48)+B(45)+B(44)+
          B(39)+B(38)+B(37)+B(36)+B(35)+B(34)+B(32)+B(30)+B(26)+B(25)+
          B(24)+B(23)+B(22)+B(21)+B(19)+B(16)+B(15)+B(11)+B(10)+B(9)+B(8)+
          B(3)+B(1)+B(0), 112),
 kDefPoly(B(111)+B(107)+B(102)+B(100)+B(99)+B(98)+B(97)+B(96)+B(95)+B(94)+
          B(93)+B(92)+B(87)+B(86)+B(82)+B(81)+B(80)+B(79)+B(77)+B(76)+
          B(75)+B(72)+B(69)+B(64), B(61)+B(58)+B(56)+B(54)+B(53)+B(52)+
          B(51)+B(49)+B(46)+B(43)+B(40)+B(39)+B(37)+B(36)+B(35)+B(34)+
          B(33)+B(31)+B(29)+B(24)+B(22)+B(21)+B(20)+B(15)+B(14)+B(12)+
          B(10)+B(6)+B(1)+B(0), 113),
 kDefPoly(B(112)+B(111)+B(110)+B(104)+B(102)+B(101)+B(100)+B(92)+B(89)+
          B(87)+B(83)+B(82)+B(80)+B(79)+B(75)+B(74)+B(73)+B(72)+B(71)+
          B(70)+B(68)+B(67)+B(65), B(60)+B(59)+B(57)+B(56)+B(55)+B(52)+
          B(50)+B(47)+B(44)+B(41)+B(36)+B(35)+B(30)+B(29)+B(26)+B(25)+
          B(24)+B(21)+B(18)+B(17)+B(16)+B(14)+B(12)+B(10)+B(7)+B(6)+
          B(0), 114),
 kDefPoly(B(114)+B(112)+B(111)+B(110)+B(108)+B(107)+B(103)+B(102)+B(98)+
          B(97)+B(96)+B(90)+B(88)+B(87)+B(86)+B(83)+B(82)+B(80)+B(79)+
          B(77)+B(75)+B(70)+B(66)+B(65)+B(64), B(61)+B(60)+B(59)+B(58)+
          B(57)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+B(43)+B(39)+B(38)+
          B(33)+B(32)+B(31)+B(29)+B(27)+B(21)+B(17)+B(14)+B(12)+B(10)+B(7)+
          B(4)+B(2)+B(1)+B(0), 115),
 kDefPoly(B(113)+B(110)+B(108)+B(106)+B(105)+B(102)+B(101)+B(100)+B(98)+
          B(96)+B(92)+B(89)+B(87)+B(86)+B(84)+B(81)+B(79)+B(78)+B(76)+
          B(75)+B(73)+B(72)+B(71)+B(70)+B(67)+B(64), B(63)+B(62)+B(61)+
          B(52)+B(47)+B(45)+B(44)+B(42)+B(40)+B(39)+B(35)+B(34)+B(33)+
          B(31)+B(29)+B(25)+B(18)+B(15)+B(14)+B(10)+B(8)+B(6)+B(1)+
          B(0), 116),
 kDefPoly(B(113)+B(111)+B(110)+B(109)+B(107)+B(106)+B(103)+B(102)+B(100)+
          B(96)+B(95)+B(94)+B(91)+B(90)+B(89)+B(86)+B(82)+B(81)+B(78)+
          B(77)+B(76)+B(75)+B(74)+B(73)+B(70)+B(67)+B(66), B(63)+B(61)+
          B(59)+B(57)+B(56)+B(55)+B(53)+B(52)+B(51)+B(50)+B(47)+B(45)+
          B(42)+B(40)+B(37)+B(35)+B(32)+B(30)+B(29)+B(25)+B(22)+B(21)+
          B(20)+B(19)+B(16)+B(15)+B(14)+B(12)+B(8)+B(5)+B(0), 117),
 kDefPoly(B(117)+B(113)+B(110)+B(108)+B(105)+B(104)+B(103)+B(102)+B(99)+
          B(98)+B(97)+B(94)+B(93)+B(91)+B(90)+B(89)+B(85)+B(84)+B(82)+
          B(81)+B(79)+B(78)+B(77)+B(74)+B(73)+B(69)+B(67)+B(64), B(63)+
          B(62)+B(61)+B(57)+B(55)+B(51)+B(50)+B(46)+B(45)+B(43)+B(42)+
          B(41)+B(37)+B(33)+B(32)+B(30)+B(27)+B(26)+B(21)+B(19)+B(18)+
          B(17)+B(15)+B(14)+B(12)+B(10)+B(8)+B(7)+B(3)+B(2)+B(1)+
          B(0), 118),
 kDefPoly(B(118)+B(111)+B(109)+B(107)+B(106)+B(105)+B(104)+B(101)+B(99)+
          B(98)+B(97)+B(94)+B(92)+B(91)+B(89)+B(83)+B(82)+B(80)+B(79)+
          B(67)+B(66), B(62)+B(61)+B(60)+B(58)+B(57)+B(52)+B(48)+B(46)+
          B(44)+B(42)+B(40)+B(39)+B(38)+B(36)+B(34)+B(33)+B(32)+B(29)+
          B(23)+B(22)+B(20)+B(19)+B(18)+B(15)+B(13)+B(12)+B(11)+B(6)+B(5)+
          B(4)+B(3)+B(1)+B(0), 119),
 kDefPoly(B(116)+B(115)+B(113)+B(112)+B(110)+B(107)+B(106)+B(104)+B(103)+
          B(101)+B(100)+B(99)+B(98)+B(90)+B(89)+B(88)+B(87)+B(82)+B(80)+
          B(79)+B(77)+B(76)+B(75)+B(74)+B(73)+B(71)+B(70)+B(68)+B(65)+
          B(64), B(63)+B(62)+B(59)+B(55)+B(54)+B(48)+B(47)+B(45)+B(44)+
          B(40)+B(39)+B(38)+B(35)+B(33)+B(29)+B(27)+B(26)+B(25)+B(24)+
          B(23)+B(22)+B(21)+B(18)+B(17)+B(15)+B(13)+B(12)+B(10)+B(8)+B(3)+
          B(2)+B(0), 120),
 kDefPoly(B(118)+B(117)+B(114)+B(113)+B(112)+B(110)+B(109)+B(104)+B(103)+
          B(101)+B(99)+B(97)+B(96)+B(95)+B(93)+B(92)+B(91)+B(90)+B(89)+
          B(87)+B(85)+B(84)+B(82)+B(81)+B(79)+B(73)+B(72)+B(68)+B(67)+
          B(66)+B(64), B(60)+B(58)+B(57)+B(56)+B(54)+B(53)+B(52)+B(51)+
          B(49)+B(48)+B(47)+B(45)+B(44)+B(38)+B(37)+B(36)+B(35)+B(33)+
          B(32)+B(31)+B(30)+B(27)+B(26)+B(24)+B(23)+B(22)+B(20)+B(19)+
          B(18)+B(16)+B(15)+B(12)+B(6)+B(5)+B(4)+B(2)+B(0), 121),
 kDefPoly(B(121)+B(118)+B(114)+B(112)+B(109)+B(106)+B(103)+B(102)+B(101)+
          B(100)+B(97)+B(95)+B(90)+B(89)+B(87)+B(83)+B(81)+B(80)+B(79)+
          B(78)+B(77)+B(76)+B(75)+B(74)+B(72)+B(71)+B(70)+B(69)+B(68)+
          B(66)+B(64), B(61)+B(57)+B(51)+B(50)+B(47)+B(46)+B(43)+B(39)+
          B(38)+B(37)+B(36)+B(34)+B(33)+B(32)+B(30)+B(28)+B(27)+B(24)+
          B(22)+B(20)+B(18)+B(17)+B(14)+B(12)+B(11)+B(9)+B(7)+B(2)+
          B(0), 122),
 kDefPoly(B(122)+B(121)+B(120)+B(119)+B(118)+B(117)+B(116)+B(113)+B(112)+
          B(111)+B(109)+B(106)+B(105)+B(103)+B(100)+B(98)+B(97)+B(95)+
          B(93)+B(92)+B(90)+B(87)+B(86)+B(85)+B(83)+B(81)+B(78)+B(77)+
          B(75)+B(74)+B(73)+B(72)+B(71)+B(70)+B(69)+B(68)+B(67)+B(65)+
          B(64), B(63)+B(62)+B(60)+B(55)+B(52)+B(51)+B(49)+B(47)+B(45)+
          B(43)+B(42)+B(41)+B(37)+B(36)+B(35)+B(34)+B(32)+B(28)+B(27)+
          B(26)+B(24)+B(23)+B(21)+B(20)+B(16)+B(13)+B(10)+B(9)+B(8)+B(7)+
          B(5)+B(2)+B(0), 123),
 kDefPoly(B(123)+B(121)+B(120)+B(118)+B(117)+B(116)+B(115)+B(112)+B(111)+
          B(110)+B(109)+B(107)+B(104)+B(102)+B(101)+B(100)+B(99)+B(98)+
          B(97)+B(94)+B(90)+B(87)+B(86)+B(84)+B(83)+B(82)+B(79)+B(75)+
          B(72)+B(71)+B(70)+B(64), B(63)+B(56)+B(54)+B(51)+B(50)+B(47)+
          B(45)+B(44)+B(42)+B(39)+B(38)+B(36)+B(34)+B(33)+B(29)+B(26)+
          B(24)+B(20)+B(16)+B(14)+B(11)+B(10)+B(8)+B(7)+B(6)+B(4)+B(2)+
          B(0), 124),
 kDefPoly(B(124)+B(123)+B(121)+B(119)+B(118)+B(116)+B(115)+B(114)+B(107)+
          B(105)+B(104)+B(103)+B(102)+B(99)+B(98)+B(96)+B(94)+B(93)+B(89)+
          B(83)+B(82)+B(81)+B(80)+B(79)+B(78)+B(75)+B(74)+B(73)+B(72)+
          B(70)+B(69)+B(68)+B(64), B(63)+B(59)+B(56)+B(55)+B(52)+B(51)+
          B(50)+B(49)+B(48)+B(44)+B(42)+B(38)+B(37)+B(36)+B(33)+B(31)+
          B(29)+B(27)+B(26)+B(25)+B(23)+B(21)+B(19)+B(18)+B(16)+B(14)+
          B(11)+B(8)+B(7)+B(6)+B(4)+B(1)+B(0), 125),
 kDefPoly(B(124)+B(122)+B(121)+B(120)+B(119)+B(117)+B(113)+B(110)+B(108)+
          B(105)+B(103)+B(102)+B(101)+B(97)+B(93)+B(91)+B(90)+B(88)+B(86)+
          B(84)+B(82)+B(81)+B(79)+B(77)+B(76)+B(75)+B(73)+B(72)+B(71)+
          B(69)+B(67)+B(64), B(63)+B(62)+B(61)+B(60)+B(58)+B(56)+B(55)+
          B(52)+B(51)+B(48)+B(47)+B(45)+B(44)+B(42)+B(41)+B(40)+B(39)+
          B(37)+B(33)+B(32)+B(30)+B(29)+B(28)+B(27)+B(26)+B(25)+B(24)+
          B(23)+B(19)+B(18)+B(17)+B(16)+B(14)+B(13)+B(11)+B(9)+B(8)+B(7)+
          B(4)+B(2)+B(1)+B(0), 126),
 kDefPoly(B(125)+B(124)+B(121)+B(116)+B(115)+B(105)+B(103)+B(101)+B(94)+
          B(93)+B(91)+B(90)+B(88)+B(87)+B(86)+B(85)+B(77)+B(73)+B(72)+
          B(70)+B(68)+B(67), B(63)+B(62)+B(61)+B(59)+B(57)+B(53)+B(52)+
          B(51)+B(49)+B(48)+B(46)+B(44)+B(41)+B(39)+B(38)+B(36)+B(35)+
          B(30)+B(27)+B(25)+B(23)+B(20)+B(19)+B(13)+B(12)+B(11)+B(10)+B(8)+
          B(7)+B(5)+B(4)+B(3)+B(2)+B(0), 127),
 kDefPoly(B(127)+B(122)+B(121)+B(118)+B(117)+B(116)+B(109)+B(108)+B(107)+
          B(106)+B(104)+B(103)+B(102)+B(101)+B(96)+B(93)+B(92)+B(91)+B(89)+
          B(86)+B(85)+B(80)+B(78)+B(77)+B(76)+B(75)+B(74)+B(73)+B(72)+
          B(71)+B(66), B(60)+B(56)+B(53)+B(52)+B(50)+B(47)+B(45)+B(41)+
          B(39)+B(38)+B(37)+B(35)+B(34)+B(33)+B(30)+B(28)+B(25)+B(24)+
          B(23)+B(21)+B(20)+B(19)+B(14)+B(13)+B(10)+B(8)+B(5)+B(4)+B(2)+
          B(1)+B(0), 128),
};
// lint -restore

// The number of polynomials in POLYS[].
SELECTANY const int CRC::N_POLYS = sizeof (poly_list) / sizeof (poly_list[0]);

// The externally visible name of poly_list.
// This guarantees that the size of poly_list is opaque.
SELECTANY const struct CRC::Poly *const CRC::POLYS = poly_list;

// The "constructor" for a CRC with an default polynomial.
CRC *CRC::Default(int degree, size_t roll_length) {
  ASSERT1(32 == degree);

  CRC *crc = CRCImpl::NewInternal(CRC::POLYS[degree].lo, CRC::POLYS[degree].hi,
                                  degree, roll_length);  // Build the table
  return crc;
}

// The "constructor" for a CRC with an arbitrary polynomial.
CRC *CRC::New(uint64 lo, uint64 hi, int degree, size_t roll_length) {
  return CRCImpl::NewInternal(lo, hi, degree, roll_length);
}

// Internal version of the "constructor".
CRCImpl *CRCImpl::NewInternal(uint64 lo, uint64 hi,
                             int degree, size_t roll_length) {
  ASSERT1(8 <= degree && degree <= 64);  // precondition
  ASSERT1(lo != 0 || hi != 0);            // precondition
  // Generate the tables for extending a CRC by 4 bytes at a time.
  // Why 4 and not 8?  Because Pentium 4 has such small caches.
  struct CRC_pair t[4][256];
  for (int j = 0; j != 4; j++) {      // for each byte of extension....
    t[j][0].lo = 0;                   // a zero has no effect
    t[j][0].hi = 0;
    for (int i = 128; i != 0;  i >>= 1) {  // fill in entries for powers of 2
      if (j == 0 && i == 128) {
        t[j][i].lo = lo;  // top bit in first byte is easy---it's the polynomial
        t[j][i].hi = hi;
      } else {
                  // each successive power of two is derive from the previous
                  // one, either in this table, or the last table
        struct CRC_pair pred;
        if (i == 128) {
          pred = t[j-1][1];
        } else {
          pred = t[j][i << 1];
        }
        // Advance the CRC by one bit (multiply by X, and take remainder
        // through one step of polynomial long division)
        if (pred.lo & 1) {
          t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63) ^ lo;
          t[j][i].hi = (pred.hi >> 1) ^ hi;
        } else {
          t[j][i].lo = (pred.lo >> 1) ^ (pred.hi << 63);
          t[j][i].hi = pred.hi >> 1;
        }
      }
    }
    // CRCs have the property that CRC(a xor b) == CRC(a) xor CRC(b)
    // so we can make all the tables for non-powers of two by
    // xoring previously created entries.
    for (int i = 2; i != 256;  i <<= 1) {
      for (int k = i+1; k != (i << 1); k++) {
        t[j][k].lo = t[j][i].lo ^ t[j][k-i].lo;
        t[j][k].hi = t[j][i].hi ^ t[j][k-i].hi;
      }
    }
  }

  // Copy the newly built tables in t[] into an appropriate
  // CRC implenentation object.
  CRCImpl *result = 0;
  CRC32 *crc32 = 0;
  crc32 = new CRC32();
  for (int i = 0; i != 256; i++) {
    crc32->table0_[i] = static_cast<uint32>(t[0][i].lo);
    crc32->table1_[i] = static_cast<uint32>(t[1][i].lo);
    crc32->table2_[i] = static_cast<uint32>(t[2][i].lo);
    crc32->table3_[i] = static_cast<uint32>(t[3][i].lo);
  }
  result = crc32;

  // "result" is now a CRC object of the right type to handle
  // the polynomial of the right degree.

  result->roll_length_ = roll_length;
  result->degree_ = degree;
  result->poly_lo_ = lo;
  result->poly_hi_ = hi;

  // Build the table for extending by zeroes.
  // Entry i=a-1+3*b (a in {1, 2, 3}, b in {0, 1, 2, 3, ...}
  // contains a polynomial Pi such that multiplying
  // a CRC by Pi mod P, where P is the CRC polynomial, is equivalent to
  // appending a*2**(2*b+SMALL_BITS) zero bytes to the original string.
  // Entry is generated by calling ExtendByZeroes() twice using
  // half the length from the previous entry.
  int pos = 0;
  for (uint64 inc_len = (1 << SMALL_BITS); inc_len != 0; inc_len <<= 2) {
    result->Empty(&lo, &hi);
    for (int k = 0; k != 3; k++) {
      result->ExtendByZeroes(&lo, &hi, (size_t) (inc_len >> 1));
      result->ExtendByZeroes(&lo, &hi, (size_t) (inc_len >> 1));
      crc32->zeroes_[pos] = static_cast<uint32>(lo);
      pos++;
    }
  }

  // Calculate the entries in the roll table, used for rolling checksums
  // of a fixed length.
  // Extend the powers of two in the one-byte extension table by the roll
  // length.
  int bit = 256;
  do {
    bit >>= 1;
    result->ExtendByZeroes(&t[0][bit].lo, &t[0][bit].hi, roll_length);
  } while (bit != 0);
  // Calculate the non-powers of two using CRC(a xor b) == CRC(a) xor CRC(b)
  for (int i = 2; i != 256;  i <<= 1) {
    for (int j = i+1; j != (i << 1); j++) {
      t[0][j].lo = t[0][i].lo ^ t[0][j-i].lo;
      t[0][j].hi = t[0][i].hi ^ t[0][j-i].hi;
    }
  }
  // Now xor the CRC of (binary) 100000001 followed by
  // the roll length of zeroes.   This will be xored into every
  // entry.   This will simultaneously roll out the CRC
  // of the empty string that's been pushed one byte too far,
  // and roll in the CRC of the empty string in the correct place again.
  result->Empty(&lo, &hi);
  const uint8 x = 0x80;
  result->Extend(&lo, &hi, &x, 1);
  result->ExtendByZeroes(&lo, &hi, roll_length);
  for (int i = 0; i != 256; i++) {
    t[0][i].lo ^= lo;
    t[0][i].hi ^= hi;
  }

  // Put the roll table into the object.
  for (int i = 0; i != 256; i++) {
    crc32->roll_[i] = static_cast<uint32>(t[0][i].lo);
  }

  return result;
}

// The CRC of the empty string is always the CRC polynomial itself.
void CRCImpl::Empty(uint64 *lo, uint64 *hi) const {
  ASSERT1(hi);
  ASSERT1(lo);

  *lo = this->poly_lo_;
  *hi = this->poly_hi_;
}

//  The 32-bit implementation

void CRC32::Extend(uint64 *lo, uint64 *hi, const void *bytes, size_t length)
                      const {
  ASSERT1(hi);
  ASSERT1(lo);

  hi;   // unreferenced formal parameter

  const uint8 *p = static_cast<const uint8 *>(bytes);
  const uint8 *e = p + length;
  uint32 l = static_cast<uint32>(*lo);
  // point x at MIN(first 4-byte aligned byte in string, end of string)
  const uint8 *x = p + ((zero_ptr - p) & 3);
  if (x > e) {
    x = e;
  }
  // Process bytes until finished or p is 4-byte aligned
  while (p != x) {
    int c = (l & 0xff) ^ *p++;
    l = this->table0_[c] ^ (l >> 8);
  }
  // point x at MIN(last 4-byte aligned byte in string, end of string)
  x = e - ((e - zero_ptr) & 3);
  // Process bytes 4 at a time
  while (p < x) {
    uint32 c = l ^ *reinterpret_cast<const uint32*>(p);
    p += 4;
    l = this->table3_[c & 0xff] ^
        this->table2_[(c >> 8) & 0xff] ^
        this->table1_[(c >> 16) & 0xff] ^
        this->table0_[c >> 24];
  }

  // Process the last few bytes
  while (p != e) {
    int c = (l & 0xff) ^ *p++;
    l = this->table0_[c] ^ (l >> 8);
  }
  *lo = l;
}

void CRC32::ExtendByZeroes(uint64 *lo, uint64 *hi, size_t length) const {
  ASSERT1(hi);
  ASSERT1(lo);

  // Process the low order SMALL_BITS of the length by simply
  // using Extend() on an array of bytes that are zero.
  size_t small_part = (length & ((1 << SMALL_BITS)-1));
  if (small_part != 0) {
    this->Extend(lo, hi, zeroes, small_part);
  }
  length >>= SMALL_BITS;
  if (length != 0) {          // if the length was at least 2**SMALL_BITS
    uint32 l = static_cast<uint32>(*lo);
    uint32 onebit = 1;
    onebit <<= this->degree_ - 1;
    // For each pair of bits in length
    // (after the low-oder bits have been removed)
    // we lookup the appropriate polynomial in the zeroes_ array
    // and do a polynomial long multiplication (mod the CRC polynomial)
    // to extend the CRC by the appropriate number of bits.
    for (size_t i = 0; length != 0; i += 3, length >>= 2) {
      size_t c = length & 3;       // pick next two bits
      if (c != 0) {                // if they are not zero,
                                   // multiply by entry in table
        uint32 m = this->zeroes_[c+i-1];
        uint32 result = 0;
        for (uint32 one = onebit; one != 0; one >>= 1) {
          if ((l & one) != 0) {
            result ^= m;
          }
          if (m & 1) {
            m = (m >> 1) ^ static_cast<uint32>(poly_lo_);
          } else {
            m = (m >> 1);
          }
        }
        l = result;
      }
    }
    *lo = l;
  }
}

void CRC32::Roll(uint64 *lo, uint64 *hi, uint8 o_byte, uint8 i_byte) const {
  ASSERT1(hi);
  ASSERT1(lo);

  hi;   // unreferenced formal parameter

  uint32 l = static_cast<uint32>(*lo);
  // Roll in i_byte and out o_byte
  *lo = this->table0_[(l & 0xff) ^ i_byte] ^ (l >> 8) ^ this->roll_[o_byte];
}

}  // namespace omaha

